Topological data analysis

Topological data analysis is a new area of study aimed at having applications in areas such as data mining and computer vision. The main problems are:

how one infers high-dimensional structure from low-dimensional representations; and
how one assembles discrete points into global structure.

The human brain can easily extract global structure from representations in a strictly lower dimension, i.e. we infer a 3D environment from a 2D image from each eye. The inference of global structure also occurs when converting discrete data into continuous images, e.g. dot-matrix printers and televisions communicate images via arrays of discrete points.

The main method used by topological data analysis is:

Replace a set of data points with a family of simplicial complexes, indexed by a proximity parameter.
Analyse these topological complexes via algebraic topology — specifically, via the new theory of persistent homology.
Encode the persistent homology of a data set in the form of a parameterized version of a Betti number which will be called a barcode.

1 Point cloud data
2 Persistent homology
3 See also
4 References
5 Further reading

Point cloud data

Data is often represented as points in a Euclidean n-dimensional space E_n. The global shape of the data may provide information about the phenomena that the data represent.

One type of data set for which global features are certainly present is the so-called point cloud data coming from physical objects in 3D. E.g. a laser can scan an object at a set of discrete points and the cloud of such points can be used in a computer representation of the object. Point cloud data refers to any collection of points in E_n or a (perhaps noisy) sample of points on a lower-dimensional subset.

For point clouds in low-dimensional spaces there are numerous approaches for inferring features based on planar projections in the fields of computer graphics and statistics. Topological data analysis is needed when the spaces are high-dimensional or too twisted to allow planar projections.

To convert a point cloud in a metric space into a global object, use the point cloud as the vertices of a graph whose edges are determined by proximity, then turn the graph into a simplicial complex and use algebraic topology to study it. An alternative approach is the minimum spanning tree-based method in the geometric data clustering.^[1] If a group of data points forms a cluster, then the geometry of this point cloud can be determined.

Persistent homology

See homology for an introduction to the notation.

Persistent homology essentially calculates homology groups at different resolutions to see which features persist for long periods of time. It is assumed that important features and structures are the ones that persist. We define persistent homology as follows:

Let $K^l$ be a filtration. The p-persistent kth homology group of $K^l$ is $H_k^{l,p}=Z_k^l/(B_k^{l,p}\cap Z_k^l)$ .

If we let $z$ be a nonbounding $k$ -cycle created at time $I$ by simplex $\sigma$ and let $z'\sim z$ be a homologous $k$ -cycle that becomes a boundary cycle at time $J$ by simplex $\tau$ , then we can define the persistence interval associated to $z$ as $(I,J)$ . We call $\sigma$ the creator of $z$ and $\tau$ the destroyer of $z$ . If $z$ does not have a destroyer, its persistence is $\infty$ .

Instead of using an index-based filtration, we can use a time-based filtration. Let $K$ be a simplicial complex and $K^\rho=\{ \sigma^i\in K|\rho (\sigma^i)\le \rho \}$ be a filtration defined for an associated map $\rho�: S(K)\rightarrow \mathbb{R}$ that maps simplices in the final complex to real numbers. Then for all real numbers $\pi \ge 0$ , the $\pi$ -persistent kth homology group of $K^\rho$ is $H_k^{\rho, \pi}=Z_k^\rho /(B_k^{\rho %2B \pi }\cap Z_k^\rho )$ . The persistence of a $k$ -cycle created at time $\rho_i$ and destroyed at $\rho_j$ is $\rho_j - \rho_i$ . ^[2]

There are various software packages for computing persistence intervals of a finite filtration, such as jPlex, Dionysus and the Perseus software projects.

References

^ C. T. Zahn (1971): "Graph-theoretical methods for detecting and describing gestalt clusters", IEEE Transactions on Computers, pp. 68-86, Vol. 20, No. 1
^ Afra J. Zomorodian (2005): Topology for Computing. Cambridge Monographs on Applied and Computational Mathematics.

Topological data analysis

Contents

Point cloud data

Persistent homology

See also

References

Further reading